POI2014 Salad Bar
题目大意：
有一个长度为$n$的字符串，每一位只会是$p$或$j$。你需要取出一个子串$S$（从左到右或从右到左一个一个取出），使得不管是从左到右还是从右往左取，都保证每时每刻已取出的$p$的个数不小于$j$的个数。你需要最大化$|S|$。
题解：
首先很容易想到把每一个$p$看做$1$，把每一个$j$看做$-1$，之后通过前缀和（$sum$）来判断是否满足条件。
如果一个子串$[L,R]$是合法的，那么必然满足以下条件:
$$\forall k \in [L+1,R] ,sum_i \le sum_k \le sum_j$$
反之，只要满足了上述条件，这个子串一定合法。
于是，我们不难想到，枚举一个每一个$L$，对于每一个$L$，向后找$R$。
对于一个$L$， 找$L$右边第一个$sum$比$i$小的下标$k$。
那么显然，$k$以及$k$右边的点，都无法做$i$的右端点。
因而只能在区间$[L+1,k-1]$找右端点。
因为要使$sum_L \le sum_x \le sum_R$，显然区间中$sum$最大的哪一个即为右端点。（若最大有多个，取最右边的那个。）
这个可以用反证法：
假设我们不以最大的为右端点。
那么有两种情况：
- 最大的点在你取的点的左边，那么这样最大的点在$[L+1，R]$之间，但是$sum$值却比$R$ 大，显然是不合法的。
- 最大的点在你取的点的右边。那么我们取最大的点一定可以满足，并且还比当前点更优，因而还不如取最大的那个。
综上所述，我们得到了一种复杂度为$O(nlog n)$的算法。
首先可以$O(n)$ 预处理出每一个左端点的右端点存在的可能区间。
之后对于每一个左端点，我们在区间查询最大值即可。（这个可以用线段树等数据结构来写，单次查询为$O(logn)$）。
但实际上还有一种O(n)的写法：
不妨把问题具象化：
把前缀和看做是高度，由于每一次更改的值绝对值为$1$ ，因而一个个$sum$连成了一幅连续的折线图。
我们把向上凸起的称为山峰，向下凹的称为山谷。
那么对于每一个点，我们要找的实际上是，往右延伸时，在不出现比当前点高度矮的山谷的前提下，最高的山峰的位置。
这个可以用$dp$来写。
- 若$str_i=p$ ，那么我们有 $ peak_i= \begin{cases} { peak_{ i+1} } & { (sum _{peak_{i+1}}>sum_{peak _{nxt_{i} } }) } \\ {peak_{nxt_i} }&{ (sum_{peak_{i+1}} \le sum_{peak_{nxt_{i} } }) } \end{cases}$
- 若$str_i=j$ ，那么我们有$peak\ _i = i$
其中$nxt_i$表示，下一个出现的与当前点高度相同的点的位置。
我们可以$O(n)$预处理出$nxt$数组，又可以$O(n)$实现$dp$值的转移。
综上题目即可解。
Code:
这里只给出O(n)的代码：
|
|